This present invention relates to cryptography, and more particularly to authentication and to establishing a shared cryptographic key by two parties by means of a (possibly short) secret about which the two parties have information.
Consider two parties, Alice and Bob. Alice and Bob may be implemented via hardwired and/or software programmable circuitry capable of performing processing logic. Suppose Alice and Bob desire to communicate securely over an insecure network, but their only means of verifying each other's identity consists of a short secret password (e.g., a 4-digit PIN number), for which Alice knows the password itself, and Bob knows at least some “password verification information”. In particular, it is possible that neither of them knows a public key corresponding to the other party, and neither has a certified public key (i.e., a public key whose certificate can be verified by the other party). In this scenario, Alice needs to be concerned not only with eavesdroppers that may try to steal the password by listening in on her communications, but also with the party with whom she is communicating, since a priori she cannot even be sure she is communicating with Bob. Bob's situation is similar.
If Alice and Bob shared a high-strength cryptographic key (i.e., a long secret), then this problem could be solved using standard solutions well-known in the art for setting up a secure channel, such as the protocol of Bellare and Rogaway [4]. However, since Alice and Bob only have information about a short secret password, they may also be concerned with offline dictionary attacks. An offline dictionary attack occurs when an attacker obtains some password verification information that can be used to perform offline verification of password guesses. For example, suppose Alice and Bob share a password π, and an attacker somehow obtained a hash of the password h(π), where h is some common cryptographic hash function such as SHA-1 [39]. Then the attacker could go offline and run through a dictionary of possible passwords {π1, π2, . . . }, testing each one against h(π). For instance, to test if πi is the correct password, the attacker computes h(πi) and checks if h(πi)=h(π). In general, the password verification information obtained by the attacker may not be as simple as a hash of a password, and an attacker may not always be able to test all possible passwords against the password verification information, but if he can test a significant number of passwords, this is still considered an offline dictionary attack. Wu [47] describes how effective an offline dictionary attack can be.
Accordingly, it is desirable to establish a protocol for communication between Alice and Bob so that they can bootstrap information about a short secret (the password) into a long secret (a cryptographic key) that can be used to provide a secure channel.
Such protocols are called in the art password-authenticated key exchange (PAKE) protocols. Informally, a PAKE protocol is secure if the only feasible way to attack the protocol is to run a trivial online dictionary attack of simply iteratively guessing passwords and attempting to impersonate one of the parties. (This type of attack can generally be detected and stopped by well-known methods, as discussed below.) The problem of designing a secure PAKE protocol was proposed by Bellovin and Merritt [6] and by Gong et al. [21], and has since been studied extensively.
If the PAKE protocol designates one of Alice or Bob as a client, and the other one as a server, and if it guarantees that a compromise of the server does not reveal any information that could be used to impersonate the client without performing at least an offline dictionary attack, then the protocol is said to have resilience against server compromise. Such a protocol is also called an augmented PAKE protocol. This problem of designing an augmented PAKE protocol was proposed by Bellovin and Merritt [7], and has also been studied extensively. In the foregoing, many techniques in the art that have been proposed to solve this problem will be discussed.
One major application of PAKE is to bootstrap a public key infrastructure (PKI). Specifically, a user can use a PAKE protocol to set up a secure channel to a credential store to securely download his certificate for a public key and the corresponding private key. Thus a user does not need to be concerned about storing his private key on his local device, where it may be stolen—laptop theft is a major problem—or it may simply be lost, say if the hard drive of the user's device is damaged from falling on the ground. One example of a system that uses a PAKE protocol in such a way is Plan9, and more specifically, SecureStore in Plan9 [14].
Previous Solutions
Many common password authentication techniques in the art are unilateral authentication techniques, that is, only one party (a user or client) is authenticated to the other party (a server), but not vice-versa. (On the other hand, a PAKE protocol as described above is a mutual authentication technique.) For convenience we will apply the labels client and server to describe the two principals Alice and Bob, bearing in mind, however, that these terms are merely convenient labels.
One simple technique is for the client to send a password to the server without any form of cryptographic protection. This type of authentication is used in some older Internet applications, as well as many web-based mail applications. However, this is insecure against an eavesdropper on the network. This technique might be acceptable on channels wherein eavesdropping is relatively difficult.
A more advanced technique is challenge-response, wherein the server sends a challenge to the client, and the client responds with a message depending on the challenge and the password, for instance the hash of the challenge and password concatenated. This type of authentication is used in some operating systems to enable network access. However, this technique is vulnerable to an offline dictionary attack by an eavesdropper since the challenge and its corresponding response, together, make password verification information. An attacker eavesdropping on the communication could take the transcript of the conversation (i.e., the challenge and the hash value), and try all possible passwords until one matches.
A more secure technique involves sending a password to the server over an anonymous secure channel, wherein the server has been verified using a public key. This type of authentication is used in some remote terminal applications, as well as web-based applications, and it depends intrinsically on the ability of the client to verify the server's public key. When used on the web, the public key of the server is certified by a certification authority that is presumably trusted by the client. For remote terminal applications, there typically is no trusted third party, and security relies on the client recognizing the public key, perhaps with a “fingerprint,” or hash, of the public key. As long as the server's public key can be verified, this type of authentication is secure. However, if the server's public key cannot be verified, then this type of authentication is vulnerable to an attacker that is able to impersonate the server. For instance, in the web-based application, this could occur if the attacker obtains a certificate improperly, and in a remote terminal application, this could occur if the client machine has not previously stored the public key of the server.
Accordingly, it is desirable to find a Password Authenticated Key Exchange (PAKE) algorithm secure against offline dictionary attack. Such security should be achieved at least when no participants are compromised. If a party has been compromised by an adversary, the adversary may obtain some password verification information which will defeat the security against an offline dictionary attack. However, if for example the server is compromised, it is desirable that while the offline dictionary attack security may be defeated, the protocol would be resilient to server comprise.
It will be understood that it is the objective of any PAKE protocol to be secure against offline dictionary attacks. Since the PAKE problem was introduced, it has been studied extensively, and many PAKE protocols have been proposed, e.g., [7, 21, 20, 24, 25, 34, 45, 46, 33, 32]. Many of these protocols have been shown to be insecure [10, 40]. It is therefore desirable to develop a protocol that can be proven secure according to some reasonable cryptographic assumption. Many of these PAKE protocols also claim to be resilient to server compromise, e.g., [7, 25, 46, 33, 38], and it is also desirable to develop protocols that can be proven to be resilient to server compromise according to some reasonable cryptographic assumption.
More recent PAKE protocols have proofs of security, based on certain well-known cryptographic assumptions, although some of these proofs assume the existence of ideal hash functions or ideal ciphers (i.e. black-box perfectly-random functions or keyed permutations, respectively). Such a means is commonly used by those skilled in the cryptographic arts to provide a mathematical proof of security of their work to others skilled in the art. A few recent papers [2, 12, 1] present refinements of the EKE protocol of [7] and prove security based on the Diffie-Hellman (DH) assumption [16]. The first assumes both ideal ciphers and ideal hashes, while the others assume only ideal hashes. Other papers [35, 51] present refinements of the OKE protocol of [34] and prove security based on the RSA assumption [42]. These all assume ideal hashes. Another paper [30] presents new protocol based on a variant of the Cramer-Shoup cryptosystem [15] and proves security based on the decisional DH assumption (see, e.g., [11]), assuming only a public random string (not an ideal hash function). Some variants of the [30] protocol are presented in [18, 29, 13]. Another password-authenticated key exchange protocol was developed in [19] and proven secure based on trapdoor permutations without any setup assumptions, but with a restriction that concurrent sessions with the same password are prohibited.
In terms of resilience to server compromise, the following papers contain protocols that have proofs of security assuming the existence of ideal hash functions [12, 37, 35].
For the purposes of bootstrapping PKI, it has been noticed that one may not need a full PAKE protocol, but just a password-based protocol designed solely for downloading a set of credentials (or at least a static cryptographic key used to decrypt an encrypted set of credentials). One protocol that does this is [17], and a variant is [26]. Security for these protocols relies on a non-standard assumption related to Diffie Hellman.
Previous Password Authenticated Key Exchange schemes have been implemented in commercial products and have been specified for use within several technology standards. The SRP protocol [46] has been implemented for a variety of applications, including telnet and ftp [50]. There are also two IETF RFCs related to SRP: RFC 2944 [48] and RFC 2945 [49]. The SPEKE protocol [24] has been implemented and is available [41] for licensing. The PAK protocol [12] has been implemented and is used in the SecureStore protocol [14].
There are currently PAKE standards being developed in the IEEE P1363 working group and in ISO/IEC 11770-4 working group. The IEEE P1363 working group is developing the P1363.2 draft standard specifications for password-based public key cryptographic techniques, which is likely to include PAK [12], SPEKE [24], SRP [46], AMP [33], and the Ford-Kaliski/Jablon protocol [17,26], along with variations of these protocols. The ISO/IEC 11770-4 draft standards will most likely include all of these except PAK.
FIG. 1 illustrates a PAKE protocol described in [38]. In this protocol, a client C (e.g., Alice) and a server S (e.g. Bob) authenticate each other by proving to each other that each knows password authentication information H1(π) wherein π is the password and H1( ) is a hash function. Also, the client C and the server S generate a long secret key K which can be used for symmetric encryption between C and S in a subsequent session.
The function H1( ) maps passwords into a finite cyclic group Gq of an order q. Gq can be a subgroup of the multiplicative group ZP* of the ring Zp, of integers modulo a prime number p. Element g is a generator of Gq, Symbols Hi(e.g. H2, H3, H4) denote various hash functions. For example, the following hash functions can be used:Hi(x)=H(ASCII(i)∥x)  (1)where H( ) is the SHA-1 function or some other hash function. The functions H1 and H2 have values in Gq, so if Gq is a subgroup of Zp*, then for i=1, 2 one can setHi(x)=H(ASCII(i)∥x)mod p.  (2)Other suitable hash functions are described in [38].
For better security, neither the client C nor the server S need to store the password π. The client C can receive the password and the server's name S as input from a user via a keyboard or some other input device. For each client C having a password π=πC, the server stores a database record πS[C] which may include the value H1(πC). In FIG. 1, the server stores instead the inverse value H1(πC)−1 to improve the computational efficiency (as will be made clear below in connection with step 130S).
Step 110C is performed by the client C as in the Diffie-Hellman (DH) secret key exchange protocol. More particularly, the client generates a random element x of Zq (i.e., x is an integer from 0 to q−1), and computes α=gx. At step 120C, the client computes H1(π) and then computes m=α·H1(π). At step 124C, the client sends its name C and the value m to the server.
At step 110S, the server performs some simple checking on m (using a function ACCEPTABLE( )), and aborts if this check fails. The check can be that m mod p is not 0. At step 120S, the server generates a random y in Zq and computes μ=gy. At step 130S, the server uses its stored value H1(πC)−1 to compute the client's value α (see step 110C):α=m·H1(πC)−1.At step 140S, the server computes the DH shared key value σ=αy (this value is equal to gxy). At step 150S, the server computes a value k=H2(<C,S,m,μ,σ,H1(πC)−1>). At step 160S, the server sends the values μ, k to the client to prove that the server knows H1(πC)−1 (and hence H1(πC) assuming that inverting H1(πC)−1 is easy in Gq; of note, the inversion can be easily done in Zp* using the Extended Euclidean Algorithm).
The client verifies the server's proof at steps 130C, 140C. More particularly, at step 130C, the client computes σ as μx. At step 140C, the client computes H1(π)−1, then H2(<C,S,m,μ,σ,H1(π)−1>), and aborts if this latter value does not equal the server's k. At step 160C, the client generates a value k′=H3(<C,S,m,μ,σ,H1(πC)−1>) and sends this value to the server (step 170C) as a proof that the client knows H1(π). At step 170S, the server verifies the proof by computing H3(<C,S,m,μ,σ,H1(πC)−1>) and checking that this value equals k′.
At respective steps 180C, 180S, the client and the server each generate a shared session key K=H4(<C,S,m,μ,σ,H1(πC)−1>). K can be a long key.
Of note, the information send over the network (i.e. the values C, m, μ, k, k′) is difficult to use for an offline dictionary attack. For example, the use of σ in the expressions for k and k′ (steps 150S, 160C), and the use of the random number y in generating σ, make it difficult to mount an offline dictionary attack even if the communications between C and S are intercepted.
However, if an adversary compromises the server S, the adversary can obtain the value H1(π)−1 from πS[C] and compute H1(π). The adversary can then impersonate the client C because the protocol does not require the client to prove knowledge of any information about π other than H1(π). Hence, the protocol is not resilient against server compromise.
FIG. 2 illustrates a modified protocol “PAK-Z” from [38]. This is an augmented PAKE protocol, requiring the client to prove knowledge of additional information about π to the server. For each client C, the server's record πS[C] includes a value H1(<C,πC>)−1, a signature verification key pk for verifying digital signatures according to some signature scheme, and an encryption E<C,πC>(sk) of a signing key sk corresponding to pk:E<C,πC>(sk)=H7(<C,πC>)⊕sk  (3)where H7( ) is a suitable hash function, e.g. as in (1) or (2). This encryption is called “one-time pad”.
The client performs steps 110C-124C as in FIG. 1. The server performs steps 110S-150S as in FIG. 1. In addition, at steps 210S, 214S the server computes an encryption c′ of E<C,πC>(sk):c′=H5(<C,S,m,μ,σ,H1(<C,π>)−1>)⊕E<C,πC>(sk)  (4)where H5 is some hash function (e.g. as in (1) or (2)). At step 160S, the server sends the value c′ together with μ and k to the client.
The client performs steps 130C, 140C as in FIG. 1. At step 210C, the client decrypts c′ to c=E<C,πC>(sk):E<C,πC>(sk)=H5(<C,S,m,μ,σ,H1(<C,π>)−1>)⊕c′  (5)At step 220C, the client decrypts c=E<C,πC>(sk) to the signing key sk:sk=c⊕H7(<C,π>)−1  (6)The client also does some validity checking on sk, and aborts if the check fails. At step 230C, the client computes a digital signature s=Sigsk(μ) on the server's DH key μ (see step 120S in FIG. 1) under the key sk. At step 240C, the client encrypts the signature s to a values′=H6(<C,S,m,μ,σ,H1(<C,π>)−1>)⊕s  (7)and sends s′ to the server (step 250C). At step 220S, the server recovers the signature s by computing:s=H6(<C,S,m,μ,σ,H1(<C,π>)−1>)⊕s′  (8)At step 230S, the server verifies the signature with the public key pk obtained from πS[C]. If the verification fails, the server aborts. The shared key generation (steps 180C, 180S) is performed as in FIG. 1.